\appendix

\section{Proofs for Section~\ref{sec:lower}}
\label{app:lower}


\begin{lemma}
\label{lem:alg+lower.single}
From any distribution in which each token starts at exactly one node
and no node has more than one token, any online token-forwarding
algorithm for $k$-gossip needs $\Omega(kn/\log n)$ rounds against a
strong adversary.
\end{lemma}
\begin{proof}
We consider an initial distribution $C$ where each token is at exactly
one node, and no node has more than one token. Let $C^*$ be an initial
token distribution in which each node has each token independently
with probability $3/4$.  By Theorem~\ref{thm:alg+lower}, any online
algorithm starting from distribution $C^*$ needs $\Omega(kn/\log n)$
rounds with high probability.  

We construct a bipartite graph on two copies of $V$, $V_1$ and
$V_2$. A node $v \in V_1$ is connected to a node $u \in V_2$ if in
$C^*$ $u$ has all the tokens that $v$ has in $C$.  We first show,
using Hall's Theorem, that this bipartite graph has a perfect matching
with very high probability.  Consider a set of $m$ nodes in $V_2$. We want to show their
neighborhood in the bipartite graph is of size at least $m$. We show
this condition holds by the following 2 cases. If $m < 3n/5$, let
$X_i$ denote the neighborhood size of node $i$. We know $\expect{X_i}
\ge 3n/4$. Then by Chernoff bound
\[\prob{X_i < m} \le \prob{X_i < 3n/5} \le e^{-\frac{\rb{1/5}^2 \expect{X_i}}{2}} = e^{-\frac{3n}{200}}\]
By union bound with probability at least $1-n\cdot e^{-3n/200}$ the
neighborhood size of every node is at least $m$. Therefore, the
condition holds in the first case. If $m \ge 3n/5$, we argue the
neighborhood size of any set of $m$ nodes is $V_1$ with high
probability. Consider a set of $m$ nodes, the probability that a given
token $t$ is missing in all these $m$ nodes is $(1/4)^m$. Thus the
probability that any token is missing in all these nodes is at most
$n(1/4)^m \le n(1/4)^{3n/5}$. There are at most $2^n$ such sets. By
union bound, with probability at least $1-2^n\cdot n(1/4)^{3n/5} =
1-n/2^{n/5}$, the condition holds in the second case.

By applying the union bound, we obtain that with positive probability
(in fact, high probability), $C^*$ takes $\Omega(nk/\log n)$ rounds
and there is a perfect matching $M$ in the above bipartite graph.  By
the probabilistic method, thus both $C^*$ and $M$ exist.  Given such
$C^*$ and $M$, we complete the proof as follows.  For $v\in V_2$, let
$M(v)$ denote the node in $V_1$ that got matched to $v$.  If there is
an algorithm $A$ that runs in $T$ rounds from starting state $C$, then
we can construct an algorithm $A^*$ that runs in the same number of
rounds from starting state $C^*$ as follows. First every node $v$
deletes all its tokens except for those which $M(v)$ has in $C$. Then
algorithm $A^*$ runs exactly as $A$.  Thus, the lower bound of
Theorem~\ref{thm:alg+lower}, which applies to $A^*$ and $C^*$, also
applies to $A$ and $C$. \qed
\end{proof}

\begin{LabeledProof}{Theorem~\ref{thm:lower.single}}
In this theorem, we extend our proof in
Lemma~\ref{lem:alg+lower.single} to the inital distibution $C$ where
each token starts at exactly one node, but nodes may have multiple
tokens. We prove this theorem by the following two cases.

The first case is when at least $n/2$ nodes start with some
token. This implies that $k\ge n/2$.  Let us focus on the $n/2$ nodes
with tokens. Each of them has at least one unique token. By the same
argument used in Lemma~\ref{lem:alg+lower.single}, disseminating these
$n/2$ distinct tokens to $n$ nodes takes $\Omega(n^2/\log n)$
rounds. Thus, in this case the number of rounds needed is
$\Omega(kn/\log n)$.

The second case is when less than $n/2$ nodes start with some
token. In this case, the adversary can group these nodes together, and
treat them as one super node. There is only one edge connecting this
super node to the rest of the nodes. Thus, the number of useful token
exchanges provided by this super node is at most one in each round. If
there exsits an algorithm that can disseminate $k$ tokens in
$o(kn/\log n)$ rounds, then the contribution by the super node is
$o(kn/\log n)$. And by the same argument used in
Lemma~\ref{lem:alg+lower.single} we know dissemination of $k$ tokens
to $n/2$ nodes (those start with no tokens) takes $\Omega(kn/\log n)$
rounds. Thus, the theorem also holds in this case. \qed
\end{LabeledProof}

\section{Proofs for Section~\ref{sec:centralized}}
\label{app:centralized}

\smallskip
\noindent
{\em Evolution graph}: Let $V$ be the set of nodes. Consider a dynamic
network of $l$ rounds numbered $1$ through $l$ and let $G_i$ be the
communication graph for round $i$. The evolution graph for this
network is a directed capacitated graph $G$ with $2l+1$ levels
constructed as follows. We create $2l+1$ copies of $V$ and call them
$V_0, V_1, V_2, \dots, V_{2l}$. $V_i$ is the set of nodes at level $i$ and
for each node $v$ in $V$, we call its copy in $V_i$ as $v_i$. For $i =
1, \ldots, l$, level $2i-1$ corresponds to the beginning of round $i$
and level $2i$ corresponds to the end of round $i$. Level $0$
corresponds to the network at the start. Note that the end of a
particular round and the start of the next round are represented by
different levels. There are three kinds of edges in the graph. First,
for every round $i$ and every edge $(u,v) \in G_i$, we place two
directed edges with unit capacity each, one from $u_{2i-1}$ to
$v_{2i}$ and another from $v_{2i-1}$ to $u_{2i}$. We call these edges
{\em broadcast edges} as they will correspond to broadcasting of
tokens; the unit capacity on each such edge will ensure that only one
token can be sent from a node to a neighbor in one round. Second, for
every node $v$ in $V$ and every round $i$, we place an edge with
infinite capacity from $v_{2(i-1)}$ to $v_{2i}$. We call these edges
{\em buffer edges} as they ensure tokens can be stored at a node from
the end of one round to the end of the next. Finally, for every node
$v \in V$ and every round $i$, we also place an edge with unit
capacity from $v_{2(i-1)}$ to $v_{2i-1}$. We call these edges as {\em
  selection edges} as they correspond to every node selecting a token
out of those it has to broadcast in round $i$; the unit capacity
ensures that in a given round a node must send the same token to all
its neighbors. Figure \ref{fig:evolution} illustrates our
construction, and Lemma~\ref{lem:level.steiner} explains its
usefulness.

\begin{figure}[ht]
\begin{center}
\includegraphics[width=5in]{level.jpg}
\caption{An example of how to construct the evolution graph from a
  sequence of communication graphs.}
\label{fig:evolution}
\end{center}
\end{figure}

\begin{LabeledProof}{Lemma~\ref{lem:level.steiner}}
Assume that $k$ tokens can be sent to all of their destinations in $l$
rounds and fix one broadcast schedule that achieves this. We will
construct $k$ directed Steiner trees as required by the lemma based on
how the tokens reach their destinations and then argue that they all
can be packed in the evolution graph respecting the edge
capacities. For a token $i$, we construct a Steiner tree $T^i$ as
follows.  For each level $j \in \{0, \ldots, 2l\}$, we define a set
$S^i_j$ of nodes at level $j$ inductively starting from level $2l$
backwards.  $S^i_{2l}$ is simply the copies of the destination nodes
for token $i$ at level $2l$. Once $S^i_{2(j+1)}$ is defined, we define
$S^i_{2j}$ (respectively $S^i_{2j+1}$) as: for each $v_{2(j+1)} \in
S^i_{2(j+1)}$, include $v_{2j}$ (respectively nothing) if token $i$
has reached node $v$ by round $j$, or include a node $u_{2j}$
(respectively $u_{2j+1}$) such that $u$ has token $i$ at the end of
round $j$ which it broadcasts in round $j+1$ and $(u,v)$ is an edge of
$G_{j+1}$. Such a node $u$ can always be found because whenever
$v_{2j}$ is included in $S^i_{2j}$, node $v$ has token $i$ by the end
of round $j$ which can be proved by backward induction staring from $j
= l$. It is easy to see that $S^i_0$ simply consists of the copy of
the source node of token $i$ at level $0$. $T^i$ is constructed on the
nodes in $\cup_{j = 0}^{j = 2l} S^i_j$. If for a vertex $v$,
$v_{2(j+1)} \in S^i_{2(j+1)}$ and $v_{2j} \in S^i_{2j}$, we add the
buffer edge $(v_{2j},v_{2(j+1)})$ in $T^i$. Otherwise, if $v_{2(j+1)}
\in S^i_{2(j+1)}$ but $v_{2j} \notin S^i_{2j}$, we add the selection
edge $(u_{2j},u_{2j+1})$ and broadcast edge $(u_{2j+1},v_{2(j+1)})$ in
$T^i$, where $u$ was the node chosen as described above. It is
straightforward to see that these edges form a directed Steiner tree
for token $i$ as required by the lemma which can be packed in the
evolution graph. The argument is completed by noting that any unit
capacity edge cannot be included in two different Steiner trees as we
started with a broadcast schedule where each node broadcasts a single
token to all its neighbors in one round, and thus all the $k$ Steiner
trees can be simultaneously packed in the evolution graph respecting
the edge capacities.

Next assume that $k$ Steiner trees as in the lemma can be packed in
the evolution graph respecting the edge capacities. We construct a
broadcast schedule for each token from its Steiner tree in the natural
way: whenever the Steiner tree $T_i$ corresponding to token $i$ uses a
broadcast edge $(u_{2j-1},v_{2j})$ for some $j$, we let the node $u$
broadcast token $i$ in round $j$. We need to show that this is a
feasible broadcast schedule. First we observe that two different
Steiner trees cannot use two broadcast edges starting from the same
node because every selection edge has unit capacity, thus there are no
conflicts in the schedule and each node is asked to broadcast at most
one token in each round. Next we claim by induction that if node
$v_{2j}$ is in $T^i$, then node $v$ has token $i$ by the end of round
$j$. For $j = 0$, it is trivial since only the copy of the source node
for token $i$ can be included in $T^i$ from level $0$. For $j > 0$, if
$v_{2j}$ is in $T^i$, we must reach there by following the buffer edge
$(v_{2(j-1)},v_{2j})$ or a broadcast edge $(u_{2j-1},v_{2j})$. In the
former case, by induction node $v$ has token $i$ after round $j-1$
itself. In the latter case, node $u$ which had token $i$ after round
$j-1$ by induction was the neighbor of node $v$ in $G_j$ and $u$
broadcast token $i$ in round $j$, thus implying node $v$ has token $i$
after round $j$. From the above claim, we conclude that whenever a
node is asked to broadcast a token in round $j$, it has the token by
the end of round $j-1$. Thus the schedule we constructed is a feasible
broadcast schedule. Since the copies of all the destination nodes of a
token at level $2l$ are the terminals of its Steiner tree, we conclude
all the tokens reach all of their destination nodes after round $l$.
\end{LabeledProof}

\begin{figure}[ht]
\begin{center}
\includegraphics[width=5in]{steiner.jpg}
\caption{An example of building directed Steiner tree in the evolution
  graph $G$ based on token dissemination process. Token $t$ starts
  from node $B$. Thus, the Steiner tree is rooted at $B_0$ in
  $G$. Since $B_0$ has token $t$, we include the infinite capacity
  buffer edge $(B_0,B_2)$. In the first round, node $B$ broadcasts
  token $t$, and hence we include the selection edge
  $(B_0,B_1)$. Nodes $A$ and $C$ receive token $t$ from $B$ in the
  first round, so we include edges $(B_1,A_2)$, $(B_1,C_2)$. Now
  $A_2$, $B_2$, and $C_2$ all have token $t$. Therefore we include the
  edges $(A_2,A_4)$, $(B_2,B_4)$, and $(C_2,C_4)$. In the second
  round, all of $A$, $B$, and $C$ broadcast token $t$, we include
  edges $(A_2,A_3)$, $(B_2,B_3)$, $(C_2,C_3)$. Nodes $D$ and $E$
  receive token $t$ from $C$. So we include edges $(C_3,D_4)$ and
  $(C_3,E_4)$. Notice that nodes $A$ and $B$ also receive token $t$
  from $C$, but they already have token $t$. Thus, we don't include
  edges $(C_3,B_4)$ or $(C_3,A_4)$.}
\label{fig:steiner}
\end{center}
\end{figure}

\subsection{Proofs for Section~\ref{sec:upper}}
\label{app:upper}

\begin{LabeledProof}{Lemma~\ref{lem:level.flow}}
By lemma~\ref{lem:level.steiner}, we will be done in $n + k$ rounds if
we can show that $k$ paths, one from every source vertex at level $0$
to $v_{2(n+k)}$, can be packed in the corresponding evolution graph
with $2(n+k) + 1$ levels respecting the edge capacities. For this, we
consider the evolution graph and add to it a special vertex $v_{-1}$
at level $-1$ and connect it to every source at level $0$ by an edge
of capacity 1. (Multiple edges get fused with corresponding increase
in capacity if multiple tokens have the same source.) We claim that
the value of the min-cut between $v_{-1}$ and $v_{2(n+k)}$ is at least
$k$. Before proving this, we complete the proof of the claim assuming
this.  By the max flow min cut theorem, the max flow between $v_{-1}$
and $v_{2(n+k)}$ is at least $k$. Since we connected $v_{-1}$ with
each of the $k$ token sources at level $0$ by a unit capacity edge, it
follows that unit flow can be routed from each of these sources at
level $0$ to $v_{2(n+k)}$ respecting the edge capacities. It is easy
to see that this implies we can pack $k$ paths, one from every source
vertex at level $0$ to $v_{2(n+k)}$, respecting the edge capacities.

To prove our claimed bound on the min cut, consider any cut of the
evolution graph separating $v_{-1}$ from $v_{2(n+k)}$ and let $S$ be
the set of the cut containing $v_{-1}$. If $S$ includes no vertex from
level $0$, we are immediately done. Otherwise, observe that if $v_{2j}
\in S$ for some $0 \leq j < (n+k)$ and $v_{2(j+1)} \notin S$, then the
value of the cut is infinite as it cuts the buffer edge of infinite
capacity out of $v_{2j}$. Thus we may assume that if $v_{2j} \in S$,
then $v_{2(j+1)} \in S$. Also observe that since each of the
communication graphs $G_1, \ldots, G_{n+k}$ are connected, if the
number of vertices in $S$ from level $2(j+1)$ is no more than the
number of vertices from level $2j$ and not all vertices from level
$2(j+1)$ are in $S$, we get at least a contribution of $1$ in the
value of the cut. But since the total number of nodes is $n$ and
$v_{2(n+k)} \notin S$, there must be at least $k$ such levels, which
proves the claim.
\end{LabeledProof}

\begin{LabeledProof}{Theorem~\ref{thm:flow_based}}
It is trivial to see that if $k \leq \sqrt{\log n}$, then the
algorithm will end in $nk$ rounds and each node receives all the $k$
tokens. Assume $k > \sqrt{\log n}$. By Lemma~\ref{lem:level.flow}, all
the tokens can be sent to all the nodes in $S$ using $O(n \sqrt{k \log
  n})$ rounds. Now fix a node $v$ and a token $t$. Since token $t$ is
broadcast for $2n \sqrt{(\log n)/k}$ rounds, there is a set $S^t_v$ of
at least $2n \sqrt{(\log n)/k}$ nodes from which $v$ is reachable
within those rounds.  It is clear that if $S$ intersects $S^t_v$, $v$
will receive token $t$. Since the set $S$ was picked uniformly at
random, the probability that $S$ does not intersect $S^t_v$ is at most
\[ \frac{{n - 2n\sqrt{(\log n)/k} \choose 2\sqrt{k \log n}}}{{n \choose 2\sqrt{k \log n}}} < \left(\frac{n - 2n\sqrt{(\log n)/k}}{n}\right)^{2\sqrt{k \log n}} \le \frac{1}{n^4}. \] 
Thus every node receives every token with probability $1-1/n^3$. It is
also clear that the algorithm finishes in $O(n \sqrt{k \log n})$
rounds. \qed
\end{LabeledProof}

Algorithm~\ref{alg:flow_based} can be derandomized using the standard
technique of conditional expectations, as shown in
Algorithm~\ref{alg:derandomize}.  Given a sequence of communication
graphs, if node $u$ broadcasts token $t$ for $\Delta$ rounds and every
node that receives token $t$ also broadcasts $t$ during that period,
then we say node $v$ is within $\Delta$ {\em broadcast distance} to
$u$ if and only if $v$ receives token $t$ by the end of round
$\Delta$. Let $S$ be a set of nodes, and $|S|\le 2 \sqrt{k \log
  n}$. We use $\dprob{u}{S}{T}$ to denote the probability that the
broadcast distance from node $u$ to set $X$ is greater than $2n
\sqrt{(\log n)/k}$, where $X=S\cup \cub{\mbox{pick }2\sqrt{k\log n} -
  |S|\mbox{ nodes uniformly at random from }V\setminus T}$, and
$\dsumprob{S}{T}$ denotes the sum, over all $u$ in $V$, of
$\dprob{u}{S}{T}$.

\begin{algorithm}[ht!]
\caption{Derandomized algorithm for Step~\ref{alg.step:random} in
  Algorithm~\ref{alg:flow_based}}
\label{alg:derandomize}
\begin{algorithmic}[1]
  \REQUIRE A sequence of communication graphs $G_i$, $i = 1, 2,
  \ldots$, and $k \ge \sqrt{\log n}$

  \ENSURE A set of $2\sqrt{k\log n}$ nodes $S$ such that the broadcast
  distance from every node $u$ to $S$ is within $2 n\sqrt{(\log
    n)/k}$.
  \medskip

  \STATE Set $S$ and $T$ be $\emptyset$.

  \FOR{each $v\in V$}

  \STATE $T = T \cup \{v\}$
  
  \IF{$\dsumprob{S \cup \{v\}}{T} \le \dsumprob{S}{T}$ \label{alg.step:cal}}

  \STATE $S = S\cup \{v\}$

%  \STATE Calculate $p=\dprob{V}{S \cup \{v\}}$. 
  
%  \IF{$p \ge 1- \frac{1}{n^3}$}

  \ENDIF

  \ENDFOR

  \STATE Return $S$

\end{algorithmic}
\end{algorithm}

\begin{lemma}
\label{lem:derandomize}
The set $S$ returned by Algorithm~\ref{alg:derandomize} contains at
most $2\sqrt{k\log n}$ nodes, and the broadcast distance from every
node to $S$ is at most $2n\sqrt{(\log n)/k}$.
\end{lemma}
\begin{proof}
Let us view the process of randomly selecting $2\sqrt{k\log n}$ nodes
as a computation tree. This tree is a complete binary tree of height
$n$. There are $n+1$ nodes on any root-leaf path. The level of a node
is its distance from the root. The computation starts from the
root. Each node at the $i$th level is labeled by $b_i \in \{0,1\}$,
where 0 means not including node $i$ in the final set and 1 means
including node $i$ in the set. Thus, each root-leaf path, $b_1b_2\dots
b_n$, corresponds to a selection of nodes.  For a node $a$ in the
tree, let $S_a$ (resp., $T_a$) denote the sets of nodes that are
included (resp., lie) in the path from root to $a$.

By Theorem~\ref{thm:flow_based}, we know that for the root node $r$,
we have $\dsumprob{\emptyset}{S_r} =\dsumprob{\emptyset}{\emptyset}\le
1/n^3$.  If $c$ and $d$ are the children of $a$, then $T_c$ = $T_d$,
and there exists a real $0 \le p \le 1$ such that for each $u$ in $V$,
$\dprob{u}{S_a}{T_a}$ equals $p \dprob{u}{S_c}{T_c} +
(1-p)\dprob{u}{S_d}{T_d}$.  Therefore, $\dsumprob{S_a}{T_a}$ equals $p
\dsumprob{S_c}{T_c} + (1-p) \dsumprob{S_d}{T_d}$.  We thus obtain that
$\min\{\dsumprob{S_c}{T_c},\dsumprob{S_d}{T_d}\} \le
\dsumprob{S_a}{T_a}$.  Since we set $S$ to be $X$ in $\{S_c, S_d\}$
that minimizes $\dsumprob{X}{T_c}$, we maintain the invariant that
$\dsumprob{S}{T} \le 1/n^3$.  In particular, when the algorithm
reaches a leaf $l$, we know $\dsumprob{S_l}{V}\le 1/n^3$.  But a leaf
$l$ corresponds to a complete node selection, so that
$\dprob{u}{S_l}{V}$ is 0 or 1 for all $u$, and hence
$\dsumprob{S_l}{V}$ is an integer.  We thus have $\dsumprob{S_l}{V} =
0$, implying that the broadcast distance from node $u$ to set $S_l$ is
at most $2n \sqrt{(\log n)/k}$ for every $l$.  Furthermore, $|S_l|$ is
$2 k \sqrt{\log n}$ by construction.

Finally, note that Step~\ref{alg.step:cal} of
Algorithm~\ref{alg:derandomize} can be implemented in polynomial time,
since for each $u$ in $V$, $\dprob{u}{S}{T}$ is simply the ratio of
two binomial coefficients with a polynomial number of bits.  Thus,
Algorithm~\ref{alg:derandomize} is a polynomial time algorithm with
the desired property. \qed
\end{proof}

\subsection{Proofs for Section~\ref{sec:approx}}
\label{app:approx}

\begin{LabeledProof}{Theorem~\ref{thm:approx}}
We show the following three claims: (i) In Step
\ref{alg.step:convert}, $|{\cal S}| \ge k$ with probability at least
$1-1/e^{k/4}$. This is the correctness of Algorithm \ref{alg:approx},
saying it can find the schedule to disseminate all $k$ tokens. (ii)
The number of rounds in the schedule produced by Algorithm
\ref{alg:approx} is at most $O(n^\epsilon)$ times the optimal
one. (iii) In the token dissemination schedule, the number of tokens
sent over an edge is $O(\log n)$ in any round with high probability.

First, we prove claim (i). Let $X_i$ denote the sum of non-zero
$x^*_T$'s in iteration $i$. $X=\sum_{i=1}^{2n^\epsilon} X_i$. We know
$\expect{X_i} = k/n^{\epsilon}$. Thus, $\expect{X} = 2n^\epsilon
k/n^{\epsilon} = 2k$, which is the expected number of Steiner trees in
set $\cal S$. By Chernoff bound, we have 
\[\prob{X \le k} = \prob{X \le \rb{1-\frac{1}{2}}\expect{X}} \le e^{-\frac{\rb{1/2}^2 \expect{X}}{2}} = e^{-\frac{\rb{1/2}^2   \cdot 2k}{2}} = \frac{1}{e^{k/4}}\]
Thus, $|{\cal S}| \ge k$ with probability at least $1-1/e^{k/4}$ in
Step \ref{alg.step:convert}.

Next we prove claim (ii). Let $L$ denote the number of rounds needed
by an optimal algorithm. Since in Step \ref{alg.step:lp} we used the
$O(n^\epsilon)$-approximation algorithm in \cite{cheriyan+s:steiner}
to solve $F(\cal P)$, we know $L^* \le L$. There are $2n^\epsilon$
iterations. Thus, the number of rounds needed by Algorithm
\ref{alg:approx} is at most $2n^\epsilon L^* \le 2n^\epsilon L$, which
is an $O(n^\epsilon)$-approximation on the number of rounds.

Lastly we prove claim (iii). When Algorithm \ref{alg:approx} does
randomized rounding in Step \ref{alg.step:round}, some constraint
$\sum_{T:e\in T} x_{T} \le c_{e}$ in $\cal P$ may be violated. In the
evolution graph, $c_{e} = 1$. Let $Y$ denote the sum of $x^*_T$'s in
this constraint. We have $\expect{Y}\le c_e = 1$. By Chernoff bound,
\begin{eqnarray*}
\prob{Y\ge \expect{Y} + \log n} &=& \prob{Y \ge \rb{1+\frac{\log n}{\expect{Y}}} \expect{Y}} \\
 &\le& e^{-\expect{Y}\sqb{\rb{1+\frac{\log n}{\expect{Y}}} \ln \rb{1+\frac{\log n}{\expect{Y}}} - \frac{\log n}{\expect{Y}}}} \le \frac{1}{n^{\log\log n}} \\
\end{eqnarray*}
Thus, the number of tokens sent over a given edge is $O(\log n)$ with
probability at least $1-1/n^{\log\log n}$. Since there are only
polynomial number of edges, no edge will carry more than $O(\log n)$
tokens in a single round with high probability. \qed
\end{LabeledProof}


